#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/5 20:40
# @USER    : Shengji He
# @File    : GenerateParentheses.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from functools import lru_cache
from typing import List
from utils import timer_decorator

"""
- String
- Dynamic Programming
- Backtracking
"""


class Solution:
    """
    Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

    For example, given n = 3, a solution set is:

    [
      "((()))",

      "(()())",

      "(())()",

      "()(())",

      "()()()"
    ]

    Constraints:
        - 1 <= n <= 8
    """

    @lru_cache(64)
    def generateParenthesis(self, n: int) -> List[str]:
        """
        Args:
            n (int):

        Returns:
            List[str]
        """
        # ans = ['('*n + ')'*n]
        # s, e = 1, 2 * n - 1
        # if n < 4:
        #     while s < n:
        #         temp = list(ans[0])
        #         temp[s] = ')'
        #         for i in range(s + 1, e):
        #             if temp[i] == ')' and temp[0: i].count('(') >= temp[0: i].count(')'):
        #                 temp[i] = '('
        #                 ans.append(''.join(temp))
        #                 temp[i] = ')'
        #         s += 1
        #     return ans
        # else:
        #     temps = self.generateParenthesis(n - 1)
        #     for t in temps:
        #         while s < n:
        #             temp = list(t)
        #             temp.insert(s, '(')
        #
        #             for i in range(s + 1, e):
        #                 if temp[0: i].count('(') >= temp[0: i].count(')'):
        #                     temp.insert(i, ')')
        #                     if ''.join(temp) not in ans:
        #                         ans.append(''.join(temp))
        #                     temp = temp[0: i] + temp[i + 1:]
        #             s += 1
        #         s = 1
        #     return ans
        if n == 0:
            return ['']
        ans = []
        for c in range(n):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(n - 1 - c):
                    ans.append('({}){}'.format(left, right))
        return ans

    @timer_decorator
    def generateParenthesis_ai(self, n: int) -> List[str]:
        result = []

        def backtrack(s: str, left: int, right: int):
            """
            Args:
                s (str): 当前生成的括号字符串
                left (int): 已使用的左括号数量
                right (int): 已使用的右括号数量
            """
            if len(s) == 2 * n:
                result.append(s)
                return
            if left < n:
                backtrack(s + '(', left + 1, right)
            if right < left:
                backtrack(s + ')', left, right + 1)

        backtrack('', 0, 0)
        return result

    @timer_decorator
    def generateParenthesis_dp(self, n: int) -> List[str]:
        """通过自底向上的方式逐步构建解，避免了递归的栈开销"""
        if n == 0:
            return []
        # 初始化动态规划表
        dp = [[] for _ in range(n + 1)]
        dp[0] = ['']  # 0对括号时只有空字符串
        for i in range(1, n + 1):
            current = set()  # 避免重复
            for j in range(i):
                # 遍历所有可能的左右拆分方式：左半部分j对，右半部分i-j-1对
                for left in dp[j]:
                    for right in dp[i - j - 1]:
                        # 组合形式："(" + left + ")" + right
                        current.add(f'({left}){right}')
            dp[i] = list(current)
        return dp[n]


if __name__ == '__main__':
    S = Solution()
    n = 4
    # print(S.generateParenthesis(n))
    print(S.generateParenthesis_ai(n))
    print(S.generateParenthesis_dp(n))
    print('done')
